#include <stdio.h>
#include <stdlib.h>

#define OK 0;
#define ERR_MEM 1;
#define ERR_OUTOFSIZE 2;

typedef int Status;

typedef int DataType;

typedef struct node
{
	DataType data;
	struct node * prev, * next;
} Node;

typedef Node * List;

Status init(List * first)
{
	*first = (List) malloc(sizeof(Node));

	if(first == NULL)
	{
		return ERR_MEM;
	}

	(*first)->prev = *first;
	(*first)->next = *first;
	(*first)->data = 0;

	return OK;
}

Node * locate(List first, int index)
{
	int i, desc;
	Node * p = first;

	i = 0;

	desc = index < 0;

	if(desc)
	{
		index = -index;
	}

	while(i < index)
	{
		p = desc ? p->prev : p->next;
		if(p == first)
		{
			return NULL;
		}
		++i;
	}

	return p;
}

Status insert(List first, int index, DataType data)
{
	Node * p, * q;

	if(index == 0)
	{
		return ERR_OUTOFSIZE;
	}

	p = locate(first, index < 0 ? index + 1 : index - 1);
	if(p == NULL)
	{
		return ERR_OUTOFSIZE;
	}

	q = (Node *) malloc(sizeof(Node));

	q->data = data;

	if(index < 0)
	{
		q->next = p;
		q->prev = p->prev;
		p->prev->next = q;
		p->prev=q;
	}
	else
	{
		q->prev = p;
		q->next = p->next;
		p->next->prev = q;
		p->next = q;
	}

	return OK;
}

int length(List first)
{
	int i = 0;
	Node * p = first;
	while((p = p->next) != first)
	{
		++i;
	}

	return i;
}

Status del(List first, int index)
{
	Node * p;

	if(index == 0)
	{
		return ERR_OUTOFSIZE;
	}

	p = locate(first, index);

	if(p == NULL)
	{
		return ERR_OUTOFSIZE;
	}

	p->next->prev = p->prev;
	p->prev->next = p->next;
	free(p);

	return OK;
}

int search(List first, Node * node)
{
	int i = 0;
	Node * p = first;

	while((p = p->next) != first)
	{
		++i;
		if(p == node)
		{
			break;
		}
	}

	return p == first ? 0 : i;
}

Status append(List first, DataType data)
{
	return insert(first, -1, data);
}

Status prepend(List first, DataType data)
{
	return insert(first, 1, data);
}

int main(void)
{
	List first;
	int i, l;

	init(&first);
	
	append(first, 111);
	append(first, 123);
	append(first, 333);
	prepend(first, 444);
	prepend(first, 555);
	prepend(first, 666);

	printf("%d\n", first->next->data);
	printf("%d\n", length(first));

	printf("%d\n", del(first, 1));
	
	printf("%d\n", length(first));

	printf("search: %d\n", search(first, locate(first, 4)));

	l = length(first);
	for(i = 1; i <= l; ++i)
	{
		printf("%d: %d\n",i , locate(first, i)->data);
	}
	
	for(i = -1; i >= -l; --i)
	{
		printf("%d: %d\n",i , locate(first, i)->data);
	}

	return 0;
}